
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1703. -- [Usaco2007 Mar]Ranking the Cows -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1703: [Usaco2007 Mar]Ranking the Cows</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>87&nbsp;&nbsp;<span class=green>Solved: </span>67<br>[<a href='submitpage.php?id=1703'>Submit</a>][<a href='problemstatus.php?id=1703'>Status</a>][<a href='bbs.php?id=1703'>Discuss</a>]</center><h2>Description</h2><div class=content>
Each of Farmer John's N cows (1 <= N <= 1,000) produces milk at a
different positive rate, and FJ would like to order his cows according
to these rates from the fastest milk producer to the slowest.

FJ has already compared the milk output rate for M (1 <= M <= 10,000)
pairs of cows.  He wants to make a list of C additional pairs of
cows such that, if he now compares those C pairs, he will definitely
be able to deduce the correct ordering of all N cows.  Please help
him determine the minimum value of C for which such a list is
possible.

</div><h2>Input</h2><div class=content>
* Line 1: Two space-separated integers: N and M

* Lines 2..M+1: Two space-separated integers, respectively: X and Y.
        Both X and Y are in the range 1...N and describe a comparison
        where cow X was ranked higher than cow Y.

</div><h2>Output</h2><div class=content>

* Line 1: A single integer that is the minimum value of C.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>5 5<br />
2 1<br />
1 5<br />
2 3<br />
1 4<br />
3 4<br />
<br />
INPUT DETAILS:<br />
<br />
FJ is comparing 5 cows and has already determined that cow 2 > cow<br />
1, cow 1 > cow 5, cow 2 > cow 3, cow 1 > cow 4, and cow 3 > cow 4<br />
(where the '>' notation means "produces milk more quickly").<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
3<br />
<br />
OUTPUT DETAILS:<br />
<br />
From the information in the 5 test results, Farmer John knows that<br />
since cow 2 > cow 1 > cow 5 and cow 2 > cow 3 > cow 4, cow 2 has<br />
the highest rank. However, he needs to know whether cow 1 > cow 3<br />
to determine the cow with the second highest rank. Also, he will<br />
need one more question to determine the ordering between cow 4 and<br />
cow 5. After that, he will need to know if cow 5 > cow 3 if cow 1<br />
has higher rank than cow 3. He will have to ask three questions in<br />
order to be sure he has the rankings: "Is cow 1 > cow 3?  Is cow 4<br />
> cow 5? Is cow 5 > cow 3?"<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1703'>Submit</a>][<a href='problemstatus.php?id=1703'>Status</a>][<a href='bbs.php?id=1703'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
